BZOJ 3595 方伯伯的Oj

Description

方伯伯正在做他的Oj。现在他在处理Oj上的用户排名问题。
Oj上注册了n个用户,编号为1~”,一开始他们按照编号排名。方伯伯会按照心情对这些用户做以下四种操作,修改用户的排名和编号:
1.操作格式为1 x y,意味着将编号为z的用户编号改为V,而排名不变,执行完该操作后需要输出该用户在队列中的位置,数据保证x必然出现在队列中,同时1,是一个当前不在排名中的编号。
2.操作格式为2 x,意味着将编号为x的用户的排名提升到第一位,执行完该操作后需要输出执行该操作前编号为z用户的排名。
3.操作格式为3 x,意味着将编号为z的用户的排名降到最后一位,执行完该操作后需要输出执行该操作前编号为z用户的排名。
4.操作格式为4 k,意味着查询当前排名为足的用户编号,执行完该操作后需要输出当前操作用户的编号。
但同时为了防止别人监听自己的工作,方伯伯对他的操作进行了加密,即将四种操作的格式分别改为了:
1 x+a y+a
2 x+a
3 x+a
4 k+a
其中a为上一次操作得到的输出,一开始a=0。
例如:
上一次操作得到的输出是5
这一次操作的输入为:1 13 15
因为这个输入是经过加密后的,所以你应该处理的操作是1 8 10
现在你截获丁方伯伯的所有操作,希望你能给出结果。

Input

输入的第1行包含2个用空格分隔的整数n和m,表示初始用户数和操作数。
此后有m行,每行是一个询问,询问格式如上所示。

Output

输出包含m行。每行包含一个整数,其中第i行的整数表示第i个操作的输出。

Sample Input

10 10
1 2 11
3 13
25
37
28
2 10
2 11
3 14
2 18
4 9

Sample Output

2
2
2
4
3
5
5
7
8
11

Hint

对于 100% 的数据,1 ≤ n ≤ 10^8,1 ≤ m ≤ 10^5
输入保证对于所有的操作 1,2,3,x 必然已经出现在队列中,同时对于所有操作 1,1 ≤ y ≤ 2 × 10^8,并且
y 没有出现在队列中。
对于所有操作 4,保证 1 ≤ k ≤ n。

Solution

本来想写两颗splay维护区间(呵呵),然而太菜了写不出
搞一些奇怪的关键字就可以只用一个splay+一个map一起愉快的玩耍了
(为什么用了map还写这么长)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
#include<bits/stdc++.h>

#define maxn 100000+5
#define maxt 300000+5
#define set(a,b) memset(a,(b),sizeof(a))

using namespace std;

typedef long long ll;

struct Splay{
int s[2],par;
int l,r,rk,sum,num;
}tr[maxt];

map<int,int> node;
int root,size,st,ed;
int n,m,ans;

void update(int x)
{

int l=tr[x].s[0],r=tr[x].s[1];
tr[x].sum=tr[l].sum+tr[r].sum+tr[x].num;
}

void rotate(int x,int &rt)
{

int p=tr[x].par,t=(tr[p].s[1]==x);
tr[p].s[t]=tr[x].s[t^1],tr[tr[x].s[t^1]].par=p;
if( p==rt ) rt=x;
if( tr[p].par ){
if( tr[tr[p].par].s[0]==p ) tr[tr[p].par].s[0]=x;
else tr[tr[p].par].s[1]=x;
}
tr[x].par=tr[p].par,tr[x].s[t^1]=p,tr[p].par=x;
update(p),update(x);
}

void splay(int x,int &rt)
{

while( x!=rt ){
int p=tr[x].par,g=tr[p].par;
if( p!=rt ){
if( (tr[p].s[0]==x)^(tr[g].s[0]==p) )
rotate(p,rt);
else rotate(x,rt);
}
rotate(x,rt);
}
}

int find(int x,int k,int w)
{

if( x==0 ) return 0;
if( tr[x].l<=k && k<=tr[x].r ) return x;
if( w<tr[x].rk ) return find(tr[x].s[0],k,w);
else return find(tr[x].s[1],k,w);
}

int find_kth(int x,int k)
{

int l=tr[x].s[0],r=tr[x].s[1];
if( k<=tr[l].sum ) return find_kth(l,k);
if( tr[l].sum+tr[x].num>=k ) return x;
return find_kth(r,k-tr[l].sum-tr[x].num);
}

void delet(int x)
{

splay(x,root);
int pre=tr[x].s[0],pos=tr[x].s[1];
while( tr[pre].s[1] ) pre=tr[pre].s[1];
while( tr[pos].s[0] ) pos=tr[pos].s[0];
if( !pre || !pos ){
if( pre ) splay(pre,root),tr[pre].s[1]=0;
else splay(pos,root),tr[pos].s[0]=0;
update(root);
}
else{
splay(pre,root),splay(pos,tr[pre].s[1]);
tr[pos].s[0]=0,update(pos),update(pre);
}
}

void insert(int &x,int l,int r,int rk,int p)
{

if( x==0 ){
x=++size,tr[x].num=r-l+1,tr[x].par=p;
tr[x].sum=tr[x].num,tr[x].l=l,tr[x].r=r,tr[x].rk=rk;
splay(x,root);
return ;
}
int t=(tr[x].rk<rk);
insert(tr[x].s[t],l,r,rk,x);
}

void split(int x,int k,int w)
{

if( k!=tr[x].l ){
insert(root,tr[x].l,k-1,tr[x].l,0);
tr[x].l=k;
}
if( k!=tr[x].r ){
insert(root,k+1,tr[x].r,k+1,0);
tr[x].r=k;
}
tr[x].num=tr[x].r-tr[x].l+1,tr[x].rk=w;
}

int main()
{

#ifndef Online_Judge
freopen("3595.in","r",stdin);
freopen("3595.out","w",stdout);
#endif
scanf("%d%d",&n,&m);
insert(root,1,n,1,0);
st=0,ed=n;
for(int i=1;i<=m;i++){
int op,x,y,k;
scanf("%d",&op);
if( op==1 ){
scanf("%d%d",&x,&y);
x-=ans,y-=ans;
if( node[x]==0 ) node[x]=x;
k=find(root,x,node[x]);
split(k,x,node[x]);
splay(k,root),ans=tr[tr[k].s[0]].sum+1;
tr[k].l=tr[k].r=y;
node[x]=0,node[y]=tr[k].rk;
}
else if( op==2 ){
scanf("%d",&x),x-=ans;
if( node[x]==0 ) node[x]=x;
k=find(root,x,node[x]);
split(k,x,node[x]);
splay(k,root),ans=tr[tr[k].s[0]].sum+1;
delet(k),insert(root,tr[k].l,tr[k].l,--st,0);
node[x]=st;
}
else if( op==3 ){
scanf("%d",&x),x-=ans;
if( node[x]==0 ) node[x]=x;
k=find(root,x,node[x]);
split(k,x,node[x]);
splay(k,root),ans=tr[tr[k].s[0]].sum+1;
delet(k),insert(root,tr[k].l,tr[k].l,++ed,0);
node[x]=ed;
}
else if( op==4 ){
scanf("%d",&x),x-=ans;
k=find_kth(root,x),splay(k,root);
ans=(tr[k].l+x-tr[tr[k].s[0]].sum-1);
}
printf("%d\n",ans);
}
return 0;
}